#include <bits/stdc++.h>

using namespace std;

const int maxn=200005;
int sa[2][maxn],rk[2][maxn];
int hei[maxn];
int cnt[maxn];
int n,k;

void calsa(int *sa,int *rk,int *Sa,int *Rk){
    for(int i=1;i<=n;i++) cnt[rk[sa[i]]]=i;
    for(int i=n;i>=1;i--){
        if(sa[i]>k)
            Sa[cnt[rk[sa[i]-k]]--]=sa[i]-k;
    }
    for(int i=n-k+1;i<=n;i++) Sa[cnt[rk[i]]--]=i;
    for(int i=1;i<=n;i++) Rk[Sa[i]]=Rk[Sa[i-1]]+(rk[Sa[i]]!=rk[Sa[i-1]]||rk[Sa[i]+k]!=rk[Sa[i-1]+k]);
}

void getHei(char *str,int *sa,int *rk){
    int k=0;
    for(int i=1;i<=n;i++){
        if(k) k--;
        if(rk[i]-1<1) continue;
        int j=sa[rk[i]-1];
        while(str[i+k]==str[j+k]) k++;
        hei[rk[i]]=k;
    }
}

int* buildSa(char *str){
    memset(cnt,0,sizeof cnt);
    for(int i=1;i<=n;i++) cnt[str[i]]++;
    for(int i=2;i<=256;i++) cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--) sa[0][cnt[str[i]]--]=i;
    for(int i=1;i<=n;i++) rk[0][sa[0][i]]=rk[0][sa[0][i-1]]+(str[sa[0][i-1]]!=str[sa[0][i]]);

    k=1;
    int p,q;
    p=0;q=1;
    while(k<n){
        calsa(sa[p],rk[p],sa[q],rk[q]);
        k<<=1;swap(p,q);
    }

    getHei(str,sa[p],rk[p]);
    return sa[p];
}

int main(){
    char *str=new char[maxn];
    scanf("%s",str+1);
    n=strlen(str+1);
    int *sa=buildSa(str);
    for(int i=1;i<=n;i++) printf("%d ",sa[i]);putchar('\n');
    for(int i=2;i<=n;i++) printf("%d ",hei[i]);putchar('\n');
    return 0;
}


